from typing import List


class Solution:
    def maxProduct(self, words: List[str]) -> int:
        def word2int(word):
            integer = 0
            for c in word:
                integer |= 1 << (ord(c) - ord('a'))
            return integer

        integers = [word2int(word) for word in words]
        lengths = [len(word) for word in words]

        groups = [set() for _ in range(26)]
        for i, word in enumerate(words):
            for c in word:
                groups[ord(c) - ord('a')].add(i)

        result = 0
        for i in range(len(words) - 1):
            for g, group in enumerate(groups):
                if integers[i] & g == 0:
                    for j in group:
                        if integers[i] & integers[j] == 0:
                            result = max(result, lengths[i] * lengths[j])
        return result


words = ["abcw","baz","foo","bar","xtfn","abcdef"]
print(Solution().maxProduct(words))

words = ["a","ab","abc","d","cd","bcd","abcd"]
print(Solution().maxProduct(words))

words = ["a","aa","aaa","aaaa"]
print(Solution().maxProduct(words))


